package offer;

public class offerII_0029 {
    class Node {
        public int val;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    };
    public Node insert(Node head, int insertVal) {
        if(head==null){
            Node node=new Node(insertVal);
            node.next=node;
            return node;
        }
        Node p=head;
        Node q=head.next;
        while(p.val<=q.val&&q!=head){
            p=p.next;
            q=q.next;
        }
        if(q.val>=insertVal||p.val<=insertVal){
            Node tmp=new Node(insertVal);
            p.next=tmp;
            tmp.next=q;
            return head;
        }
        p=p.next;
        q=q.next;
        while (true){
            if(p.val<=insertVal&&q.val>=insertVal){
                Node tmp=new Node(insertVal);
                p.next=tmp;
                tmp.next=q;
                return head;
            }
            p=p.next;
            q=q.next;
        }
    }
}
